package com.Oct_TwentyNight;

import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 08.02. 迷路的机器人
 * 设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。
 * 网格中的障碍物和空位置分别用 1 和 0 来表示。
 *
 * 返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/robot-in-a-grid-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 2022/10/30 00:12
 */

public class Solution08_02 {

    int[][] grid;
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        this.grid=obstacleGrid;
        List<List<Integer>> list=new ArrayList<>();
        if (dfs(list,0,0)) return list;
        return new ArrayList<>();
    }

    public boolean dfs(List<List<Integer>> list,int row,int col){
        List<Integer> path=new ArrayList<>();
        path.add(row);
        path.add(col);
        list.add(new ArrayList<>(path));
        if (row>grid.length-1||col>grid[row].length-1||grid[row][col]==1||grid[row][col]==-1) return false;
        if (row==grid.length-1&&col==grid[0].length-1) return true;
        if (dfs(list,row+1,col)) return true;
        list.remove(list.size()-1);
        if (dfs(list,row,col+1)) return true;
        list.remove(list.size()-1);
        grid[row][col]=-1;
        return false;
    }

    public static void main(String[] args) {
        Solution08_02 solution08_02=new Solution08_02();
        System.out.println(solution08_02.pathWithObstacles(new int[][]{{0,0,0},{0,1,0},{0,0,0}}));
    }
}
